//给你一个链表数组，每个链表都已经按升序排列。 
//
// 请你将所有链表合并到一个升序链表中，返回合并后的链表。 
//
// 
//
// 示例 1： 
//
// 输入：lists = [[1,4,5],[1,3,4],[2,6]]
//输出：[1,1,2,3,4,4,5,6]
//解释：链表数组如下：
//[
//  1->4->5,
//  1->3->4,
//  2->6
//]
//将它们合并到一个有序链表中得到。
//1->1->2->3->4->4->5->6
// 
//
// 示例 2： 
//
// 输入：lists = []
//输出：[]
// 
//
// 示例 3： 
//
// 输入：lists = [[]]
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// k == lists.length 
// 0 <= k <= 10^4 
// 0 <= lists[i].length <= 500 
// -10^4 <= lists[i][j] <= 10^4 
// lists[i] 按 升序 排列 
// lists[i].length 的总和不超过 10^4 
// 
// Related Topics 链表 分治 堆（优先队列） 归并排序 
// 👍 1746 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

import java.util.*;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution23 {
    /**
     * 解题思路：
     * 1. 将所有链表合并为一个数组
     * 2. 对一维数组进行排序
     * 3. 将排序好的数组转换为链表
     *
     * 解答成功:
     * 			执行耗时:6 ms,击败了33.70% 的Java用户
     * 			内存消耗:43 MB,击败了11.28% 的Java用户
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists2(ListNode[] lists) {
        if(lists.length == 0) return null;
        List<Integer> list = new ArrayList<>();
        for (ListNode node : lists) {
            ListNode listNode = node;
            if (listNode != null) {
                list.add(listNode.val);
                while (listNode.next != null) {
                    listNode = listNode.next;
                    list.add(listNode.val);
                }
            }
        }
        
        if(list.size() == 0) return null;

        Integer[] array = list.toArray(new Integer[0]);
        Arrays.sort(array);

        int i=0;
        ListNode rootNode = new ListNode();
        rootNode.val = array[i];
        createListNode(rootNode, array, ++i);
        return rootNode;
    }

    private void createListNode(ListNode node, Integer[] array, int i) {
        if(i == array.length) return;

        ListNode nextNode = new ListNode();
        nextNode.val = array[i];
        node.next = nextNode;
        createListNode(nextNode, array, ++i);
    }

    /**
     * 解题思路
     * 1. 将链表数组放到优先级队列中（小顶堆）
     * 2. 构建新的链表，循环取出小顶堆的数据后放入链表
     * 3. 取出后将数据对应链表的next链表在存入优先级队列中，直到全部取完
     *
     * 解答成功:
     * 			执行耗时:6 ms,击败了33.70% 的Java用户
     * 			内存消耗:43.4 MB,击败了5.49% 的Java用户
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length < 1) return null;
        // 构建优先级队列（小顶堆）
        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>(lists.length, Comparator.comparingInt(node -> node.val));

        // 放置元素
        for (ListNode listNode : lists) {
            if(listNode != null) {
                priorityQueue.add(listNode);
            }
        }

        // 构建返回链表
        ListNode headNode = new ListNode(0);
        ListNode node = headNode;
        while(!priorityQueue.isEmpty()) {
            // 拿出最小的那个
            ListNode minNode = priorityQueue.poll();
            node.next = minNode;
            node = minNode;
            // 在将这个元素的下一个元素放入队列中
            if(minNode.next != null) {
                priorityQueue.add(minNode.next);
            }
        }

        return headNode.next;
    }

    public static void main(String[] args) {
        ListNode listNode11 = new ListNode(1);
        ListNode listNode12 = new ListNode(2);
        ListNode listNode13 = new ListNode(3);
        listNode12.next = listNode13;
        listNode11.next = listNode12;

        ListNode listNode21 = new ListNode(3);
        ListNode listNode22 = new ListNode(2);
        ListNode listNode23 = new ListNode(1);
        listNode22.next = listNode23;
        listNode21.next = listNode22;

        //new Solution().mergeKLists(new ListNode[]{});
        new Solution23().mergeKLists(new ListNode[]{null});
        //new Solution().mergeKLists(new ListNode[]{listNode11, listNode21});

    }
}
//leetcode submit region end(Prohibit modification and deletion)

